/*
 * Copyright (C) 冷锋
 */
#pragma once

/************************************************************************/
/* 最小堆，T类型必须含有静态Cmp方法方法                                                                     */
/************************************************************************/
/*
typedef struct Event_T  
{
	int key;
	//int GetKey(){return key;}
	static int Cmp(Event_T*a,Event_T*b)
	{ 
		if (a->key<b->key)return -1;
		if (a->key>b->key)return 1;
		if (a->key==b->key)return 0;
	}
}Event;
*/
template<typename T>
class CMinHeap
{
public:
	CMinHeap(int iCapacity)
	{
		m_pHeapData = new T* [iCapacity];
		m_iCapacity = iCapacity;
		m_iSize = 0;
	}
	//CMinHeap( int iCapacity,Event*pEvent,int n );
	~CMinHeap()
	{
		if (m_pHeapData)
		{
			delete[]m_pHeapData;
		}
	}

	int SiftDown( int pos )
	{
		int min = Min(pos);
		while ( min!=pos && pos < m_iSize)
		{
			Swap(min,pos);
			pos = min;
			min = Min(pos);
		}
		return pos;
	}

	int SiftUp( int pos )
	{
		int parent = Parent(pos);
		//while( i>0 && m_pHeapData[i]->GetKey()<m_pHeapData[parent]->GetKey())
		while( pos>0 && T::Cmp(m_pHeapData[pos],m_pHeapData[parent])<0)
		{
			Swap(pos,parent);
			pos = parent;
			parent = Parent(pos);
		}
		return pos;
	}

	int Remove( int pos ,T**removeObj)
	{
		if ( pos<0||pos>=m_iSize )
		{
			return -1;
		}
		*removeObj = m_pHeapData[pos];
		m_pHeapData[pos]=m_pHeapData[m_iSize-1];
		m_iSize--;
		SiftUp(pos);
		SiftDown(pos);
		return 0;
	}

	int Insert(T*pEvent)//插入堆
	{
		if ( m_iSize +1> m_iCapacity )
		{
			return -1;
		}
		//int key = pEvent->GetKey();
		m_pHeapData[m_iSize] = pEvent;
		m_iSize++;
		SiftUp( m_iSize -1 );
		return 0;
	}

	T*	GetMin()//返回堆中最小元素
	{
		if ( m_iSize>0 )
		{
			return m_pHeapData[0];
		}
		return NULL;
	}
	T*	ExtractMin()//返回并且从堆中删除最小元素
	{
		if ( m_iSize == 0 )
		{
			return NULL;
		}

		T*pRet = m_pHeapData[0];

		m_pHeapData[0] = m_pHeapData[m_iSize-1];
		m_iSize--;
		SiftDown(0);
		return pRet;
	}

private:
	int		m_iCapacity; //容量
	int		m_iSize;//当前元素个数
	T**		m_pHeapData;//堆

private:
	int Left( int i )
	{
		return ((i+1)<<1)-1;
	}
	int Right( int i )
	{
		return (i+1)<<1;
	}
	int Parent( int i )
	{
		return ((i+1)>>1)-1;
	}
	int Min( int i )//比较i,Left(i),Right(i)的较小值
	{
		int min  = i;
		int left = Left(i);
		int right = Right(i);
		//if ( left<m_iSize && m_pHeapData[min]->GetKey()>m_pHeapData[left]->GetKey() )
		if ( left<m_iSize && T::Cmp(m_pHeapData[min],m_pHeapData[left])>0 )
		{
			min = left;
		}
		//if ( right<m_iSize && m_pHeapData[min]->GetKey()> m_pHeapData[right]->GetKey())
		if ( left<m_iSize && T::Cmp(m_pHeapData[min],m_pHeapData[right])>0 )
		{
			min = right;
		}
		return min;
	}
	void Swap( int i,int j )
	{
		T* p =m_pHeapData[i];
		m_pHeapData[i] = m_pHeapData[j];
		m_pHeapData[j] = p;
	}
};

